7860. Судейские проблемы

Организаторы NWERC решили усовершенствовать автоматическую проверку посылок на соревновании и теперь используют две системы: DOMjudge и Kattis. Каждая посылка оценивается обеими системами, а затем результаты сравниваются, чтобы убедиться в согласованности работы систем. Однако при настройке взаимодействия между ними произошёл сбой: теперь жюри известно только множество всех результатов от обеих систем, но не известно, какой результат к какой посылке относится.

Ваша задача – помочь определить, сколько результатов могли бы совпасть между системами.

Вход. Состоит из:

· одно целое число n (1 ≤ n ≤ 10⁵) – количество посылок;

· n строк – результаты проверки системы DOMjudge в произвольном порядке;

· n строк – результаты проверки системы Kattis также в произвольном порядке.

Каждая строка – это результат длиной от 5 до 15 символов, состоящая только из строчных латинских букв.

Выход. Выведите одно число – максимальное количество результатов, которые могли совпасть в обеих системах.

Пример входа	Пример выхода
5 correct wronganswer correct correct timelimit wronganswer correct timelimit correct timelimit	4

РЕШЕНИЕ

структуры данных

Анализ алгоритма

В задаче необходимо подсчитать, какие и сколько результатов судейства были выданы системами DOMjudge и Kattis. Если результат s был получен системой DOMjudge a раз, а системой Kattis b раз, то количество совпавших результатов s равно min(a, b).

Сначала с помощью отображения map<string, int> cnt подсчитаем количество появлений каждого результата s, выданного системой DOMjudge. Затем для каждого результата s, выданного системой Kattis, уменьшаем значение cnt[s] на единицу (если cnt[s] > 0). Количество таких уменьшений и будет равно максимальному числу результатов, совпавших в обеих системах.

Пример

Подсчитаем количество результатов, выданных системами DOMjudge и Kattis в приведённом примере.

Совпадающими оказались 4 результата.

Реализация алгоритма

Объявим отображение cnt, в котором cnt[s] будет хранить количество раз, когда результат s был выдан системой DOMjudge.

map<string, int> cnt;

Читаем количество посылок n.

cin >> n;

Подсчитываем количество результатов, выданных системой DOMjudge.

for (i = 0; i < n; i++)

{

cin >> s;

cnt[s]++;

}

Обрабатываем результаты системы Kattis.

res = 0;

for (i = 0; i < n; i++)

{

cin >> s;

Если результат s встречался в DOMjudge (то есть cnt[s] > 0), уменьшаем cnt[s] на единицу и увеличиваем счетчик res – количество результатов, которые могли бы быть одинаковыми в обеих системах.

if (cnt[s] > 0)

{

cnt[s]--;

res++;

}

}

Выводим ответ.

cout << res << endl;

Java реализация

import java.util.*;

public class Main

{

static Map<String, Integer> cnt = new HashMap<String, Integer>();

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

for(int i = 1; i <= n; i++)

{

String s = con.next();

if (!cnt.containsKey(s))

cnt.put(s, 1);

else

cnt.put(s, cnt.get(s) + 1);

}

int res = 0;

for(int i = 1; i <= n; i++)

{

String s = con.next();

if (cnt.containsKey(s) && cnt.get(s) > 0)

{

cnt.put(s, cnt.get(s) - 1);

res++;

}

}

System.out.print(res);

con.close();

}

}

Python реализация

Читаем количество посылок n.

n = int(input())

Подсчитываем количество результатов, выданных системой DOMjudge.

cnt = {}

for _ in range(n):

s = input()

cnt[s] = cnt.get(s, 0) + 1

Обрабатываем результаты системы Kattis.

res = 0

for _ in range(n):

s = input()

if cnt.get(s, 0) > 0:

cnt[s] -= 1

res += 1

Выводим ответ.

print(res)